package sort.leetcode_215_medium;

public class PartitionSolution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        //第K个最大元素对应的索引
        int target = len - k;
        return quickSelect(nums, 0, len - 1, target);
    }
    public int quickSelect(int[] nums, int lo, int hi, int target){
        if(lo >= hi){
            return nums[lo];
        }
        //选择随机"基准元素"
        int r = (int)(lo + Math.random() * (hi - lo + 1));
        swap(nums, lo, r);
        int pivotIndex = partition(nums, lo, hi);
        if(pivotIndex == target){
            //基准元素的索引 == len - k，找到第K个最大元素，返回
            return nums[pivotIndex];
        }else if(pivotIndex > target){
            //基准元素的索引 > len - k， 要找的元素在基准元素的左边
            return quickSelect(nums, lo, pivotIndex - 1 ,target);
        }else{
            //基准元素的索引 < len -k， 要找的元素在基准元素的右边
            return quickSelect(nums, pivotIndex + 1, hi, target);
        }
    }
    public int partition(int[] nums, int lo, int hi){
        int pivot = nums[lo];
        int mark = lo;
        for(int i = lo + 1; i <= hi; i++){
            if(nums[i] < pivot){
                mark++;
                swap(nums, mark, i);
            }
        }
        nums[lo] = nums[mark];
        nums[mark] = pivot;
        return mark;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
